{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**<font size=7>算法学习</font>**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font size=4px color=#949494>作者：韩思宇</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "><font color=#949494>作者注：每学习一个阶段会进行一次格式和代码的整理<br/><p style=\"text-indent:4em\">目前在第一阶段</p></font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# **数据操作**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=blue>辅助工具：随机整数列表生成器</font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint\n",
    "num = int(input(\"你想生成一个多少位的整数列表：\"))\n",
    "list = []\n",
    "for i in range(0,num-1):\n",
    "    list.append(randint(0,num))\n",
    "print(list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.已知a+b+c=100，且a^2+b^2=c^2，求a,b,c的所有自然数解"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 枚举法 <font color=red>时间复杂度O(n^3)</font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a:200,b:375,c:425\n",
      "a:375,b:200,c:425\n",
      "程序已完成，总耗时：103.856528秒\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "start_time = time.time()\n",
    "for a in range(1,501):\n",
    "    for b in range(1,501):\n",
    "        for c in range(1,501):\n",
    "            if a ** 2 + b ** 2 == c ** 2 and a+b+c == 1000:\n",
    "                print('a:%3d,b:%3d,c:%3d' % (a,b,c))\n",
    "end_time = time.time()\n",
    "print(\"程序已完成，总耗时：%f秒\"%(end_time - start_time))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 去掉C的for循环<font color=red>时间复杂度O(n^2)</font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a:200,b:375,c:425\n",
      "a:375,b:200,c:425\n",
      "程序已完成，总耗时：0.247400秒\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "start_time = time.time()\n",
    "for a in range(1,501):\n",
    "    for b in range(1,501):\n",
    "            if a ** 2 + b ** 2 == (1000 - a - b) ** 2:\n",
    "                print('a:%3d,b:%3d,c:%3d' % (a,b,1000 - a - b))\n",
    "end_time = time.time()\n",
    "print(\"程序已完成，总耗时：%f秒\"%(end_time - start_time))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " ## 2.二分法猜数字(查找数字位置)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "def binary_search(list,item):\n",
    "    low = 0\n",
    "    high = len(list)-1\n",
    "    while low <= high:\n",
    "        mid = math.ceil((low+high)/2)\n",
    "        guess = list[mid]\n",
    "        if guess == item:\n",
    "            return mid\n",
    "        if guess > item:\n",
    "            high = mid - 1\n",
    "        else:\n",
    "            low = mid - 1\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "11\n"
     ]
    }
   ],
   "source": [
    "my_list = [1,3,5,7,9,10,11,13,15,17,19,21,23,25,27,29]\n",
    "print(binary_search(my_list,21))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.选择排序<font color=red>时间复杂度O(n^2)</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=blue size=3xp>选择排序原理，每一次找出最小一个数字，并加入到新的有序列表中</font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_smallest(arr):\n",
    "    smallest = arr[0]\n",
    "    smallest_index = 0\n",
    "    for i in range(1,len(arr)):\n",
    "        if arr[i] < smallest:\n",
    "            smallest = arr[i]\n",
    "            smallest_index = i\n",
    "    return smallest_index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "def selection_sort(arr):\n",
    "    newArr = []\n",
    "    for i in range(len(arr)):\n",
    "        smallest = find_smallest(arr)\n",
    "        newArr.append(arr.pop(smallest))\n",
    "    return newArr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font size=3xp color=green>测试：使用选择排序对50000个随机五位整数的列表进行排序</font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "开始执行：对50000个随机五位整数进行排序\n",
      "程序已完成，总耗时：48.216466秒\n"
     ]
    }
   ],
   "source": [
    "from time import time\n",
    "from random import randint\n",
    "print(\"开始执行：对50000个随机五位整数进行排序\")\n",
    "list = []\n",
    "for i in range(0,49999):\n",
    "    list.append(randint(10000,59999))\n",
    "start_time = time()\n",
    "selection_sort(list)\n",
    "end_time = time()\n",
    "print(\"程序已完成，总耗时：%f秒\"%(end_time - start_time))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.递归(注意递归深度上限)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "#阶乘计算\n",
    "def fact(x):\n",
    "    return x if x<=1 else x*fact(x-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "开始计算1-2960的阶乘\n",
      "程序已完成，总耗时：0.003009秒\n"
     ]
    }
   ],
   "source": [
    "from time import time\n",
    "print('开始计算1-2960的阶乘')\n",
    "start_time = time()\n",
    "fact(2960)\n",
    "end_time = time()\n",
    "print(\"程序已完成，总耗时：%f秒\"%(end_time - start_time))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### D&C算法(快速排序)<font color=red>时间复杂度O(nlog(n))</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=blue size=3xp>D&C快速排序算法原理：选出数组第一个数字作为中间数，然后进行一次排序，分别将大于和小于中间数的数分开，再从小到大把三个数组合到一起，再选出第一个数重复以上操作(使用递归的方法)</font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "#只包含一个或者空的数组不用排序\n",
    "def quick_sort(arr):\n",
    "    if len(arr)<2:\n",
    "        return arr    #到此结束递归\n",
    "    else:\n",
    "        pivot = arr[0]\n",
    "        less = [i for i in arr[1:] if i <= pivot]\n",
    "        greater = [i for i in arr[1:] if i > pivot]\n",
    "        return quick_sort(less) + [pivot] + quick_sort(greater)    #进行递归"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font size=3xp color=green>测试：使用D&C算法排序对50000个随机五位整数的列表进行排序</font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "开始执行：对50000个随机五位整数进行排序\n",
      "程序已完成，总耗时：0.102761秒\n"
     ]
    }
   ],
   "source": [
    "from time import time\n",
    "from random import randint\n",
    "print(\"开始执行：对50000个随机五位整数进行排序\")\n",
    "list = []\n",
    "for i in range(0,49999):\n",
    "    list.append(randint(10000,59999))\n",
    "start_time = time()\n",
    "quick_sort(list)\n",
    "end_time = time()\n",
    "print(\"程序已完成，总耗时：%f秒\"%(end_time - start_time))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5.散列表"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['piker', 'mike', 'miku']\n"
     ]
    }
   ],
   "source": [
    "test = {}\n",
    "test[\"alpha\"] = 'α'\n",
    "test['beta'] = 'β'\n",
    "test['gamma'] = 'γ'\n",
    "test['words'] = ['piker','mike','miku']\n",
    "print(test['words'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# **图算法**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.广度优先搜索<font color=red>时间复杂度O(节点数+连接线数)</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=blue size=3xp>适用于非加权图的路径计算</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=blue size=3xp>原理：在扫描一个项目过后，如果是目标则返回扫描结果，如果不是目标则将该项目下的所有子项目加入扫描队列末尾</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "例：(搜寻\"MIKE\")<br/><img src=\"InkedAnnotation 2019-11-18 115055_LI.jpg\"><br/><font size=3xp color=green>创建关系</font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph = {}\n",
    "graph['YOU'] = ['BOB','ANUJ','JONNY','ANNY','ALICE']\n",
    "graph['BOB'] = ['CLAIRE']\n",
    "graph['ANUJ'] = ['CLAIRE','MIKE']\n",
    "graph['JONNY'] = []\n",
    "graph['ALICE'] = []\n",
    "graph['ANNY'] = ['TOM']\n",
    "graph['TOM'] = []\n",
    "graph['CLAIRE'] = []\n",
    "graph['MIKE'] = []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font size=3xp color=green>创建队列</font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "search_queue = deque()\n",
    "search_queue += graph[\"YOU\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font size=3xp color=green>判断是否为MIKE</font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_this_mike(name):\n",
    "    return name=='MIKE'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font size=3xp color=green>开始判断</font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "find MIKE\n"
     ]
    }
   ],
   "source": [
    "i = 0\n",
    "while search_queue:\n",
    "    person = search_queue.popleft()\n",
    "    if is_this_mike(person):\n",
    "        print('find',person)\n",
    "        i = 1\n",
    "        break\n",
    "    else:\n",
    "        search_queue += graph[person]\n",
    "if i == 0:\n",
    "    print('Not find')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=red size=10xp>代码优化</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "例：(搜寻\"MIKE\")<br/><img src=\"InkedAnnotation 2019-11-18 115055_LI.jpg\"><br/><font size=3xp color=green>优化后：</font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "#创建关系\n",
    "graph = {}\n",
    "graph['YOU'] = ['BOB','ANUJ','JONNY','ANNY','ALICE']\n",
    "graph['BOB'] = ['CLAIRE']\n",
    "graph['ANUJ'] = ['CLAIRE','MIKE']\n",
    "graph['JONNY'] = []\n",
    "graph['ALICE'] = []\n",
    "graph['ANNY'] = ['TOM']\n",
    "graph['TOM'] = []\n",
    "graph['CLAIRE'] = []\n",
    "graph['MIKE'] = []\n",
    "#判断是否为MIKE\n",
    "def is_this_mike(name):\n",
    "    return name=='MIKE'\n",
    "#搜索\n",
    "def search():\n",
    "    search_queue = deque()\n",
    "    search_queue += graph['YOU']\n",
    "    searched = [] #用于记录已经搜索过的人，防止死循环\n",
    "    while search_queue:\n",
    "        person = search_queue.popleft()\n",
    "        if person not in searched:\n",
    "            if is_this_mike(person):\n",
    "                print('find',person)\n",
    "                i = 1\n",
    "                break\n",
    "            else:\n",
    "                search_queue += graph[person]\n",
    "                searched.append(person)\n",
    "    if i == 0:\n",
    "        print('Not find')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "find MIKE\n"
     ]
    }
   ],
   "source": [
    "search()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 7.狄克斯特拉算法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=blue size=3xp>适用于无负边加权图的路径计算</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "例：<br/><img src=\"Annotation 2019-11-19 211334.png\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "找到最近路程： END → F → D → C → B → START\n",
      "最近路程距离为： 8\n"
     ]
    }
   ],
   "source": [
    "#建立路径散列表\n",
    "graph = {}\n",
    "graph[\"START\"] = {}\n",
    "graph[\"START\"][\"A\"] = 2\n",
    "graph[\"START\"][\"B\"] = 3\n",
    "graph[\"A\"] = {}\n",
    "graph[\"A\"][\"E\"] = 5\n",
    "graph[\"B\"] = {}\n",
    "graph[\"B\"][\"C\"] = 1\n",
    "graph[\"C\"] = {}\n",
    "graph[\"C\"][\"D\"] = 2\n",
    "graph[\"C\"][\"E\"] = 4\n",
    "graph[\"D\"] = {}\n",
    "graph[\"D\"][\"F\"] = 1\n",
    "graph[\"E\"] = {}\n",
    "graph[\"E\"][\"F\"] = 2\n",
    "graph[\"F\"] = {}\n",
    "graph[\"F\"][\"END\"] = 1\n",
    "graph[\"END\"] = {}\n",
    "#路程\n",
    "infinity = float(\"inf\")#无穷大\n",
    "costs = {}\n",
    "costs[\"A\"] = 2\n",
    "costs[\"B\"] = 3\n",
    "costs[\"C\"] = infinity\n",
    "costs[\"D\"] = infinity\n",
    "costs[\"E\"] = infinity\n",
    "costs[\"F\"] = infinity\n",
    "costs[\"END\"] = infinity\n",
    "#父节点\n",
    "parents = {}\n",
    "parents[\"START\"] = {}\n",
    "parents[\"A\"] = \"START\"\n",
    "parents[\"B\"] = \"START\"\n",
    "parents[\"END\"] = None\n",
    "#用于储存记录过的节点\n",
    "processed = []\n",
    "#处理代码\n",
    "def find_lowest_cost_node(costs):\n",
    "    lowest_cost = float(\"inf\")\n",
    "    lowest_cost_node = None\n",
    "    for node in costs:\n",
    "        cost = costs[node]\n",
    "        if cost < lowest_cost and node not in processed:\n",
    "            lowest_cost = cost\n",
    "            lowest_cost_node = node\n",
    "            #print('lowest_cost_node:',lowest_cost_node,'lowest_cost:',lowest_cost)\n",
    "    return lowest_cost_node\n",
    "\n",
    "node = find_lowest_cost_node(costs)\n",
    "while node is not None:\n",
    "    cost = costs[node]\n",
    "    neighbors = graph[node]\n",
    "    for n in neighbors.keys():\n",
    "        new_cost = cost + neighbors[n]\n",
    "        if costs[n] > new_cost:\n",
    "            costs[n] = new_cost\n",
    "            parents[n] = node\n",
    "    processed.append(node)\n",
    "    node = find_lowest_cost_node(costs)\n",
    "#print(parents)    #{'A': 'START', 'B': 'START', 'END': 'F', 'E': 'A', 'C': 'B', 'D': 'C', 'F': 'D'}\n",
    "#print(costs)    #{'A': 2, 'B': 3, 'C': 4, 'D': 6, 'E': 7, 'F': 7, 'END': 8}\n",
    "#数据整理\n",
    "route = parents['END']\n",
    "routes = 'END'\n",
    "while(1):\n",
    "    if route == {}:\n",
    "        break\n",
    "    routes = routes+' → '+route\n",
    "    route = parents[route]\n",
    "print('找到最近路程：',routes)\n",
    "print('最近路程距离为：',costs['END'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 8.贪婪算法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "例：<br/><img src=\"20180818151259677.png\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'KFIVE', 'KTHREE', 'KONE', 'KTWO'}\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "假设你办了个广播节目，要让全美50个州的听众都收听得到，为此，\n",
    "你需要决定在哪些广播台播出，出于预算，你要力图在尽可能少的\n",
    "广播台播出，现在广播台名单和其覆盖位置如下：\n",
    "{'KONE': ID,NV,UT}{'KTWO': WA,ID,MT},{KTHREE : OR,NV,CA}\n",
    "{KFOUR : NV,UT},{KFIVE : CA, AZ}\n",
    "\"\"\"\n",
    "# 要覆盖的州\n",
    "states_needed = set(['mt', 'wa', 'or', 'id', 'nv', 'ut', 'ca', 'az'])\n",
    "\n",
    "# 广播台清单\n",
    "stations = dict()\n",
    "stations['KONE'] = set(['id', 'nv', 'ut'])\n",
    "stations['KTWO'] = set(['wa', 'id', 'mt'])\n",
    "stations['KTHREE'] = set(['or', 'nv', 'ca'])\n",
    "stations['KFOUR'] = set(['nv', 'ut'])\n",
    "stations['KFIVE'] = set(['ca', 'az'])\n",
    "\n",
    "# 最终使用的广播台\n",
    "final_stations = set()\n",
    "\n",
    "while states_needed:  # 当还有需要的州未覆盖的时候循环\n",
    "    best_station = None  # 覆盖了最多未覆盖的州的广播台\n",
    "    states_covered = set()  # 已经覆盖了的州的集合\n",
    "    # 遍历所有广播台，找出最佳广播台并且将他的覆盖州加入已覆盖的州的集合\n",
    "    for station, states_for_station in stations.items(): \n",
    "        # 计算需要覆盖的州和每个广播台覆盖的州的交集 \n",
    "        covered = states_needed & states_for_station  \n",
    "        # 如果交集的州数量比已经覆盖的州的数量多\n",
    "        if len(covered) > len(states_covered):  \n",
    "            best_station = station  # 最佳广播台更新为这个广播台\n",
    "            states_covered = covered  # 已覆盖的州更新为交集\n",
    "    states_needed -= states_covered  # 更新为覆盖的州\n",
    "    final_stations.add(best_station)  # 更新最终结果\n",
    "\n",
    "print(final_stations)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 9.动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 背包问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 最长公共子串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "例：查找相似单词"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_max_match(src_word_list,input_word):\n",
    "    max_match = 0\n",
    "    max_match_index = 0\n",
    "    for src_word_index in range(0,len(src_word_list)):\n",
    "        src_word_len = len(src_word_list[src_word_index])\n",
    "        input_word_len = len(input_word)\n",
    "        #生成二维列表\n",
    "        cell = [0 for x in range(0,src_word_len)]#横轴\n",
    "        for temp in range(0,src_word_len):\n",
    "            cell[temp] = [0 for y in range(0,input_word_len)]#纵轴\n",
    "        for i in range(0,src_word_len):\n",
    "            for j in range(0,input_word_len):\n",
    "                if src_word_list[src_word_index][i] == input_word[j]:\n",
    "                    #先判断是否为首字母\n",
    "                    if i==0 or j==0:\n",
    "                        #若为行/列首字母\n",
    "                        cell[i][j] = 1\n",
    "                    else:\n",
    "                        #不是首字母\n",
    "                        cell[i][j] = cell[i-1][j-1]+1\n",
    "                else:\n",
    "                    #同样先判断是否为首字母\n",
    "                    if i==0 or j==0:\n",
    "                        cell[i][j] = 0\n",
    "                    else:\n",
    "                        cell[i][j] = max(cell[i-1][j],cell[i][j-1])\n",
    "                        #在每次循环中找出最大匹配值的单词及其下标\n",
    "                if max_match < cell[i][j]:\n",
    "                    max_match = cell[i][j]\n",
    "                    max_match_index = src_word_index\n",
    "    print(\"找到最匹配单词:{},其下标为:{},匹配长度为:{}\".format(src_word_list[max_match_index],max_match_index,max_match))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "请输入一个单词： monkey\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "找到最匹配单词:monday,其下标为:8,匹配长度为:4\n"
     ]
    }
   ],
   "source": [
    "src_word_list = ['apple','boy','cat','dog','exciting','default','find','photo','monday','nose','mouse','post','quick','reply','since','tell']\n",
    "input_word = input('请输入一个单词：')\n",
    "find_max_match(src_word_list,input_word)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 10.K最邻近算法(KNN)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=blue size=3xp>用于计算距离的必达哥斯拉公式：</font>\n",
    "<font color=red size=4px>$$\\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$$</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=blue size=3xp>同样，该公式也能用于多维的距离计算：</font>\n",
    "<font color=red size=4px>$$\\sqrt{(a_1-a_2)^2+(b_1-b_2)^2+...+(z_1-z_2)^2}$$</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "例：基于KNN算法的分类系统"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"knn-modle.png\" width = \"521\" height = \"405\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font size=3px color=green>如图，这是一种用来分类水果(苹果/西瓜)的模型图，给未知水果两个属性，分别为颜色(从红：0 到绿：100)和大小(从小：0 到大：100)，然后使用knn算法进行分类，图上每格距离为10，两个属性的范围都是从0到100</font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fruit_judgment(color,size):\n",
    "    #创建水果坐标系\n",
    "    fruits = ['Apple','Watermelon']\n",
    "    Apple = {}\n",
    "    Watermelon = {}\n",
    "    min_distance = [[],[],[]]#用于储存最短三个距离点，二维列表，如：min_distance[0][0]是第一个元素的类型(苹果还是西瓜),min_distance[0][1]是第一个元素的距离\n",
    "    distance_list = []#在这个数组里面，前面7个是苹果，后面7个是西瓜\n",
    "    Apple['a'] = [10,10]\n",
    "    Apple['b'] = [50,10]\n",
    "    Apple['c'] = [30,20]\n",
    "    Apple['d'] = [10,30]\n",
    "    Apple['e'] = [40,30]\n",
    "    Apple['f'] = [20,40]\n",
    "    Apple['g'] = [10,50]\n",
    "    Watermelon['a'] = [90,30]\n",
    "    Watermelon['b'] = [70,50]\n",
    "    Watermelon['c'] = [90,60]\n",
    "    Watermelon['d'] = [50,70]\n",
    "    Watermelon['e'] = [50,90]\n",
    "    Watermelon['f'] = [70,90]\n",
    "    Watermelon['g'] = [90,90]\n",
    "    fruits_index_list = ['a','b','c','d','e','f','g']\n",
    "    #分别计算长度,并找出最短三个坐标\n",
    "    '''\n",
    "    11月30日记，找出最短三个坐标的思路：\n",
    "    创建一个列表，用于记录最短的三个坐标\n",
    "    找出distance_list中的最短坐标，并提出来，加入最短坐标列表，然后把distance_list中的删除，重复操作三次\n",
    "    '''\n",
    "    for i in fruits_index_list:\n",
    "        x = Apple[i][0]\n",
    "        y = Apple[i][1]\n",
    "        distance_list.append(((color-x)**2+(size-y)**2)**0.5)\n",
    "    for i in fruits_index_list:\n",
    "        x = Watermelon[i][0]\n",
    "        y = Watermelon[i][1]\n",
    "        distance_list.append(((color-x)**2+(size-y)**2)**0.5)\n",
    "    for con in range(3):\n",
    "        min_distance[con].append(distance_list.index(min(distance_list)))#添加类型(0-13)其中0-6对应苹果a-g，7-13对应西瓜a-g\n",
    "        min_distance[con].append(min(distance_list))#添加距离\n",
    "        del(distance_list[distance_list.index(min(distance_list))])#删除元素\n",
    "    #判断是苹果还是西瓜\n",
    "    Apple_num = 0\n",
    "    Watermalon_num = 0\n",
    "    fruits_result = ''\n",
    "    fruits = ''\n",
    "    for con in range(3):\n",
    "        if min_distance[con][0]<=6:\n",
    "            Apple_num += 1\n",
    "            fruits_result += '苹果'+fruits_index_list[min_distance[con][0]]+str(Apple[fruits_index_list[min_distance[con][0]]])+' 距离：'+str(min_distance[con][1])+'\\n'\n",
    "        else:\n",
    "            Watermalon_num += 1\n",
    "            fruits_result += '西瓜'+fruits_index_list[min_distance[con][0]-6]+str(Watermelon[fruits_index_list[min_distance[con][0]-6]])+' 距离：'+str(min_distance[con][1])+'\\n'\n",
    "    if Apple_num>Watermalon_num:\n",
    "        fruits = '苹果'\n",
    "    else:\n",
    "        fruits = '西瓜'\n",
    "    print('该水果分类为{},在最近的三个水果中,有{}个为苹果,{}个为西瓜,其中具体结果如果下:\\n{}'.format(fruits,Apple_num,Watermalon_num,fruits_result))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "请输入颜色和大小(在0-100之间)，并用逗号隔开： 35,55\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "该水果分类为苹果,在最近的三个水果中,有2个为苹果,1个为西瓜,其中具体结果如果下:\n",
      "苹果f[20, 40] 距离：21.213203435596427\n",
      "西瓜d[50, 70] 距离：21.213203435596427\n",
      "苹果e[40, 30] 距离：25.495097567963924\n",
      "\n"
     ]
    }
   ],
   "source": [
    "color,size = eval(input('请输入颜色和大小(在0-100之间)，并用逗号隔开：'))\n",
    "fruit_judgment(color,size)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
